import random


def partition(sequence, l, r):
    i = random.randint(l, r)
    sequence[r], sequence[i] = sequence[i], sequence[r]
    x = sequence[r]
    i = l
    for j in range(l, r):
        if sequence[j] < x:
            sequence[i], sequence[j] = sequence[j], sequence[i]
            i += 1
    sequence[i], sequence[r] = sequence[r], sequence[i]
    return i


def _quickselect(sequence, k, l, r):
    i = partition(sequence, l, r)
    if i - l + 1 < k:
        return _quickselect(sequence, k - i + l - 1, i + 1, r)
    elif i - l + 1 > k:
        return _quickselect(sequence, k, l, i - 1)
    else:
        return sequence[i]


def quickselect(sequence, k):
    if k > len(sequence):
        return None
    return _quickselect(sequence, k, 0, len(sequence) - 1)


if __name__ == '__main__':
    s = list(range(100))
    random.shuffle(s)
    print(s)
    _k = 50
    quickselect(s, _k)
    print(f'k = {_k}:', quickselect(s, _k))
